package 力扣;

import javax.sound.midi.Soundbank;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yyq
 * @create 2022-04-12 8:46
 */
public class leetcode16 {
    public static void main(String[] args) {
        leetcode16 a=new leetcode16();
        TreeNode node = a.buildTree(new int[]{1,2,3,4}, new int[]{1,4,3,2});

    }
    public  TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        toATree(root,inorder,postorder);
        return root;
    }

    private  void toATree(TreeNode root, int[] inorder, int[] postorder) {

        if(inorder.length == 1) return;
        // 获取 root 在 inorder 的index
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i] == root.val){
                rootIndex = i;
                break;
            }
        }
        //判断 root有没有左右子树
        int left = 0;
        int right = 0;

        if(rootIndex == 0) left=-1;
        if(rootIndex == inorder.length -1) right=-1;

        if(left==-1&&right==-1) return;

        TreeNode rootRight = null;
        TreeNode rootLeft  = null;
        //该节点有右子树
        if(right == 0){
            rootRight = new TreeNode(postorder[postorder.length - 2]);
        }

        // 该节点有左子树
        int rootRightTreeLeft = -1;
        int tempIndex = 0;
        if(left == 0){
            int val=0;
            // 如果有右子树
            // 获取 root 右子树左下角的数 即中序遍历的坐标为rootIndex+1
            if (right == 0){
                rootRightTreeLeft = inorder[rootIndex+1];
                for (int i = 0; i < postorder.length; i++) {
                    if(postorder[i] == rootRightTreeLeft){
                        tempIndex = i;
                        break;
                    }
                }
                val = postorder[tempIndex -1];

            }
            // 如果无右子树
            else {
                val = postorder[postorder.length-2];
                tempIndex = postorder.length-1;
            }
            rootLeft= new TreeNode(val);
        }



        if(left==0&&rootLeft!=null){
            root.left=rootLeft;
            toATree(root.left, Arrays.copyOfRange(inorder,0,rootIndex),Arrays.copyOfRange(postorder,0,tempIndex));
        }
        if(right==0&&rootRight!=null){
            root.right=rootRight;
            toATree(root.right, Arrays.copyOfRange(inorder,rootIndex+1,inorder.length),Arrays.copyOfRange(postorder,tempIndex,postorder.length-1));
        }

    }
}
